%%%
\vspace*{-0.5cm}
\begin{enumerate}
\item (2 puncte) Preciza{\c t}i timpul de execu{\c t}ie pentru cazul cel mai nefavorabil al algoritmului \underline{naiv} de {\it string matching}.
\item (2 puncte) Calcula{\c t}i func{\c t}ia e{\c s}ec (KMP) pentru pattern-ul: \texttt{ANANABANANANA}.
\item (2 puncte) Desena{\c t}i arborele digital ({\it trie}) pentru mul{\c t}imea de pattern-uri \texttt{\{a, ab, bab, bc, bca, c, caa\}}.
\item (4 puncte) Redesena{\c t}i arborele digital de la punctul anterior {\c s}i construi{\c t}i func{\c t}ia e{\c s}ec (Aho-Corasick) pentru acesta.
\item (2 puncte) Aplica{\c t}i algoritmul Aho-Corasick folosind mul{\c t}imea de pattern-uri \texttt{\{a, ab, bab, bc, bca, c, caa\}}  peste {\c s}irul \texttt{abccab}. Utiliza{\c t}i func{\c t}ia e{\c s}ec calculat{\u a} la punctul anterior.  Preciza{\c t}i mul{\c t}imea de  pattern-uri care se potrivesc {\^ i}n {\c s}ir {\c s}i pozi{\c t}iile corespunz{\u a}toare.
\end{enumerate}
%%%

%%%
\vspace*{-0.5cm}
\begin{enumerate}
\item (2 puncte) Preciza{\c t}i timpul de execu{\c t}ie pentru cazul cel mai nefavorabil al algoritmului \underline{Boyer-Moore} de {\it string matching}.
\item (2 puncte) Calcula{\c t}i func{\c t}ia e{\c s}ec (KMP) pentru pattern-ul: \texttt{ABABCABABCABC}.
\item (2 puncte) Desena{\c t}i arborele digital ({\it trie}) pentru mul{\c t}imea de pattern-uri \texttt{\{p, pq, qpq, qr, qrp, r, rpp\}}.
\item (4 puncte) Redesena{\c t}i arborele digital de la punctul anterior {\c s}i construi{\c t}i func{\c t}ia e{\c s}ec (Aho-Corasick) pentru acesta.
\item (2 puncte) Aplica{\c t}i algoritmul Aho-Corasick folosind mul{\c t}imea de pattern-uri  \texttt{\{p, pq, qpq, qr, qrp, r, rpp\}}  peste {\c s}irul \texttt{pqrrpq}. Utiliza{\c t}i func{\c t}ia e{\c s}ec calculat{\u a} la punctul anterior.  Preciza{\c t}i mul{\c t}imea de  pattern-uri care se potrivesc {\^ i}n {\c s}ir {\c s}i pozi{\c t}iile corespunz{\u a}toare.
\end{enumerate}
%%%

%%%
\vspace*{-0.5cm}
\begin{enumerate}
\item (2 puncte) Preciza{\c t}i timpul de execu{\c t}ie pentru cazul cel mai nefavorabil al algoritmului \underline{Knuth-Morris-Pratt} de {\it string matching}.
\item (2 puncte) Calcula{\c t}i func{\c t}ia e{\c s}ec (KMP) pentru pattern-ul: \texttt{ABBABBABABBAB}.
\item (2 puncte) Desena{\c t}i arborele digital ({\it trie}) pentru mul{\c t}imea de pattern-uri \texttt{\{m, mn, nmn, no, nom, o, omm\}}.
\item (4 puncte) Redesena{\c t}i arborele digital de la punctul anterior {\c s}i construi{\c t}i func{\c t}ia e{\c s}ec (Aho-Corasick) pentru acesta.
\item (2 puncte) Aplica{\c t}i algoritmul Aho-Corasick folosind mul{\c t}imea de pattern-uri \texttt{\{m, mn, nmn, no, nom, o, omm\}}  peste {\c s}irul \texttt{mnoomn}. Utiliza{\c t}i func{\c t}ia e{\c s}ec calculat{\u a} la punctul anterior.  Preciza{\c t}i mul{\c t}imea de  pattern-uri care se potrivesc {\^ i}n {\c s}ir {\c s}i pozi{\c t}iile corespunz{\u a}toare.
\end{enumerate}
%%%

%%%
\vspace*{-0.5cm}
\begin{enumerate}
\item (2 puncte) Preciza{\c t}i timpul de execu{\c t}ie pentru cazul cel mai nefavorabil al algoritmului \underline{Rabin-Karp} de {\it string matching}.
\item (2 puncte) Calcula{\c t}i func{\c t}ia e{\c s}ec (KMP) pentru pattern-ul: \texttt{ABRACADABRABR}.
\item (2 puncte) Desena{\c t}i arborele digital ({\it trie}) pentru mul{\c t}imea de pattern-uri \texttt{\{d, de, ede, ef, efd, f, fdd\}}.
\item (4 puncte) Redesena{\c t}i arborele digital de la punctul anterior {\c s}i construi{\c t}i func{\c t}ia e{\c s}ec (Aho-Corasick) pentru acesta.
\item (2 puncte) Aplica{\c t}i algoritmul Aho-Corasick folosind mul{\c t}imea de pattern-uri \texttt{\{d, de, ede, ef, efd, f, fdd\}}  peste {\c s}irul \texttt{deffde}. Utiliza{\c t}i func{\c t}ia e{\c s}ec calculat{\u a} la punctul anterior.  Preciza{\c t}i mul{\c t}imea de  pattern-uri care se potrivesc {\^ i}n {\c s}ir {\c s}i pozi{\c t}iile corespunz{\u a}toare.
\end{enumerate}
%%%

%%%
\vspace*{-0.5cm}
\begin{enumerate}
\item (2 puncte) Preciza{\c t}i timpul de execu{\c t}ie pentru algoritmul care calculeaz{\u a} func{\c t}ia e{\c s}ec pentru  \underline{KMP}.
\item (2 puncte) Calcula{\c t}i func{\c t}ia e{\c s}ec (KMP) pentru pattern-ul: \texttt{ALABALALAABLA}.
\item (2 puncte) Desena{\c t}i arborele digital ({\it trie}) pentru mul{\c t}imea de pattern-uri \texttt{\{x, xy, yxy, yz, yzx, z, zxx\}}.
\item (4 puncte) Redesena{\c t}i arborele digital de la punctul anterior {\c s}i construi{\c t}i func{\c t}ia e{\c s}ec (Aho-Corasick) pentru acesta.
\item (2 puncte) Aplica{\c t}i algoritmul Aho-Corasick folosind mul{\c t}imea de pattern-uri \texttt{\{x, xy, yxy, yz, yzx, z, zxx\}}  peste {\c s}irul \texttt{xyzzxy}. Utiliza{\c t}i func{\c t}ia e{\c s}ec calculat{\u a} la punctul anterior.  Preciza{\c t}i mul{\c t}imea de  pattern-uri care se potrivesc {\^ i}n {\c s}ir {\c s}i pozi{\c t}iile corespunz{\u a}toare.
\end{enumerate}
%%%

%%%
\vspace*{-0.5cm}
\begin{enumerate}
\item (2 puncte) Preciza{\c t}i timpul de execu{\c t}ie pentru algoritmul \underline{Aho-Corasick}.
\item (2 puncte) Calcula{\c t}i func{\c t}ia e{\c s}ec (KMP) pentru pattern-ul: \texttt{RPPRPPRPRPPRP}.
\item (2 puncte) Desena{\c t}i arborele digital ({\it trie}) pentru mul{\c t}imea de pattern-uri \texttt{\{t, tu, utu, uv, uvt, v, vtt\}}.
\item (4 puncte) Redesena{\c t}i arborele digital de la punctul anterior {\c s}i construi{\c t}i func{\c t}ia e{\c s}ec (Aho-Corasick) pentru acesta.
\item (2 puncte) Aplica{\c t}i algoritmul Aho-Corasick folosind mul{\c t}imea de pattern-uri \texttt{\{t, tu, utu, uv, uvt, v, vtt\}}  peste {\c s}irul \texttt{tuvvtu}. Utiliza{\c t}i func{\c t}ia e{\c s}ec calculat{\u a} la punctul anterior.  Preciza{\c t}i mul{\c t}imea de  pattern-uri care se potrivesc {\^ i}n {\c s}ir {\c s}i pozi{\c t}iile corespunz{\u a}toare.
\end{enumerate}
%%%
